Scroll Progress Bar

Heap sort

Heap sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure. It works by building a max heap (for ascending order) or min heap (for descending order) from the input array, repeatedly extracting the maximum (or minimum) element from the heap and placing it at the end of the array. Here's a C++ implementation of heap sort with comments and sample output for ascending order:

Program:

#include <iostream>
#include 

// Function to heapify a subtree rooted at the given index
void heapify(std::vector& arr, int size, int rootIndex) {
    int largest = rootIndex;
    int leftChild = 2 * rootIndex + 1; // Index of the left child
    int rightChild = 2 * rootIndex + 2; // Index of the right child

    // If the left child is larger than the root
    if (leftChild < size && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }

    // If the right child is larger than the largest so far
    if (rightChild < size && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // If the largest is not the root
    if (largest != rootIndex) {
        std::swap(arr[rootIndex], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, size, largest);
    }
}

// Heap sort function
void heapSort(std::vector& arr) {
    int size = arr.size();

    // Build a max heap from the input array
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(arr, size, i);
    }

    // Extract elements from the heap one by one
    for (int i = size - 1; i > 0; i--) {
        // Move the current root (maximum element) to the end
        std::swap(arr[0], arr[i]);

        // Call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

int main() {
    std::vector arr = {64, 34, 25, 12, 22, 11, 90};

    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    // Perform heap sort
    heapSort(arr);

    std::cout << "\nSorted array (ascending order): ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}
In this code:
  • heapify is a function that takes the input array arr, its size size, and the index of a root element. It ensures that the subtree rooted at the given index satisfies the max heap property.
  • heapSort is the main sorting function that builds a max heap from the input array, repeatedly extracts the maximum element (root) and places it at the end of the array while maintaining the heap property.
  • In the main function, an input vector is provided, and both the original and sorted arrays are printed in ascending order.
Sample Output (Ascending Order): 

Original array: 64 34 25 12 22 11 90 
Sorted array (ascending order): 11 12 22 25 34 64 90
As shown in the sample output, the input vector is successfully sorted in ascending order using the heap sort algorithm.

question

answer

question2

answer2